Data collection techniques are becoming more fine-grained, resulting in higher definition, more complex datasets. Some data, such as geospatial data and other spatial data, may be represented using geometric figures such as polygons in two-dimensional space or polyhedrons in three-dimensional space. The geometric figures may be constructed, displayed, or otherwise utilized based on stored data that defines the figures.
A polygon may be defined by a collection of segments that connect to form a shape. Alternatively, a polygon may be defined by a collection of vertices that, when connected by segments, form a geometric shape. Similarly, a polygon may be defined by a combination of segments and vertices that, when supplemented with other segments and vertices, form a geometric shape.
As used herein, the term “vertex” refers to a point at which two segments meet, or a point on a polygon that is used to define the polygon. Any given polygon could be described with any number of vertices. Two segments may meet at a vertex with an angle of 180 degrees to form a larger segment that includes the two segments. Alternately, two segments are not collinear when the two segments meet at a vertex with an angle greater or less than 180 degrees. As used herein, the term “segment” refers to a connection or coupling between two vertices, or points on a polygon. A segment may be an arc segment, a line segment, a zig-zag segment, or some other representation of the connection.
Some polygons, such as convex polygons, may be defined by unordered segments or vertices. In a convex polygon, every internal angle is less than 180 degrees, such that an order may be implied even if the collection of vertices or segments is unordered. Other polygons, such as concave polygons, may be defined by a collection of ordered vertices, segments, or a combination thereof. A concave polygon has at least one internal angle that is greater than 180 degrees, and the order of the vertices or segments may indicate which angle(s) are greater than 180 degrees.
Once defined, polygons may be used to perform specialized operations on a dataset. For example, searches may be performed for particular data items that are inside of the polygon, for particular data items that are near the edge of the polygon, or for particular data items that are outside of the polygon. The specialized operations may be performed to determine, for each item in the dataset, whether or not the item is inside of the polygon, near the edge of the polygon, or outside of the polygon. As geometric shapes become more complex, with hundreds, thousands, or even millions or more vertices, performing these specialized operations may consume large amounts of resources, in terms of processor cycles, memory, and, more generally, time. Even worse, performing these specialized operations may not always be possible, regardless of how much time is consumed, in certain circumstances with given hardware and software resources. In one example, due to intense demands on the resources, hardware or software may fail before completing a specialized operation on a polygon with over 10,000 vertices.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.